/*-------------------------------------------------------------------------
 *
 * gindatapage.c
 *	  处理 GIN 帖子树页面的例程。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *			src/backend/access/gin/gindatapage.c
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/gin_private.h"
#include "access/ginxlog.h"
#include "access/xloginsert.h"
#include "lib/ilist.h"
#include "miscadmin.h"
#include "storage/predicate.h"
#include "utils/rel.h"

/*
 * 存储在叶子页面上的发布列表的最小、最大和目标大小，以字节为单位。
 *
 * 代码可以处理任何大小，但当存储多个较小的列表时，随机访问效率更高，而不是一个大列表。如果由于插入而使得发布列表超过最大大小，则将其拆分为两个。如果发布列表小于最小大小，则与下一个发布列表合并。
 */
#define GinPostingListSegmentMaxSize 384
#define GinPostingListSegmentTargetSize 256
#define GinPostingListSegmentMinSize 128

/*
 * 至少有这么多项适合GinPostingListSegmentMaxSize字节长的段。这在估算N项所需空间时至少会使用。
 */
#define MinTuplesPerSegment ((GinPostingListSegmentMaxSize - 2) / 6)

/*
 * 用于操作发布树叶子页面的工作结构。
 */
typedef struct
{
	dlist_head	segments;		/* 一系列leafSegmentInfos */

	/*
	 * 以下字段表示当需要进行页面拆分时，段是如何在页面之间分割的。
	 * 由leafRepackItems填充。
	 */
	dlist_node *lastleft;		/* 左页上的最后一个段 */
	int			lsize;			/* 左页上的总大小 */
	int			rsize;			/* 右页上的总大小 */

	bool		oldformat;		/* 页面在磁盘上是预9.4格式 */

	/*
	 * 如果我们需要表示重建的叶子页面的WAL数据，它将由computeLeafRecompressWALData存储在这里。
	 */
	char	   *walinfo;		/* 缓冲区开始 */
	int			walinfolen;		/* 和长度 */
} disassembledLeaf;

typedef struct
{
	dlist_node	node;			/* 链表指针 */

	/*-------------
	 * 'action'表示此内存段相对于磁盘上的状态。它是GIN_SEGMENT_*动作代码之一：
	 *
	 * UNMODIFIED	无更改
	 * DELETE		该段将被移除。'seg'和'items'被忽略
	 * INSERT		这是一个全新的段
	 * REPLACE		这用新内容替换现有段
	 * ADDITEMS		类似REPLACE，但没有项被移除，我们详细跟踪
	 *				添加到该段的项，在'modifieditems'中
	 *-------------
	 */
	char		action;

	ItemPointerData *modifieditems;
	uint16		nmodifieditems;

	/*
	 * 以下字段表示此段中的项。如果'items'不为NULL，它包含此段中项的palloc'd数组。
	 * 如果'seg'不为NULL，它以已压缩的格式包含项。它可以指向一个已修改的磁盘页面，或一个在内存中的palloc'd段。
	 * 如果两者都设置，则它们必须表示相同的项。
	 */
	GinPostingList *seg;
	ItemPointer items;
	int			nitems;			/* 'items'中的项数，如果items != NULL */
} leafSegmentInfo;

static ItemPointer fc_dataLeafPageGetUncompressed(Page fc_page, int *fc_nitems);
static void fc_dataSplitPageInternal(GinBtree fc_btree, Buffer fc_origbuf,
								  GinBtreeStack *fc_stack,
								  void *fc_insertdata, BlockNumber fc_updateblkno,
								  Page *fc_newlpage, Page *fc_newrpage);

static disassembledLeaf *fc_disassembleLeaf(Page fc_page);
static bool fc_leafRepackItems(disassembledLeaf *fc_leaf, ItemPointer fc_remaining);
static bool fc_addItemsToLeaf(disassembledLeaf *fc_leaf, ItemPointer fc_newItems,
						   int fc_nNewItems);

static void fc_computeLeafRecompressWALData(disassembledLeaf *fc_leaf);
static void fc_dataPlaceToPageLeafRecompress(Buffer fc_buf, disassembledLeaf *fc_leaf);
static void fc_dataPlaceToPageLeafSplit(disassembledLeaf *fc_leaf,
									 ItemPointerData fc_lbound, ItemPointerData fc_rbound,
									 Page fc_lpage, Page fc_rpage);

/*
 * 从叶子数据页面读取TIDs到单个未压缩数组。TIDs以升序返回。
 *
 * advancePast是一个提示，表示调用者只对TIDs > advancePast感兴趣。要返回所有项，请使用ItemPointerSetMin。
 *
 * 注意：此函数仍然可以返回小于advancePast的项，这些项与感兴趣的项在同一个发布列表中，因此调用者仍然必须检查所有返回的项。
 * 但传递它允许此函数跳过整个发布列表。
 */
ItemPointer GinDataLeafPageGetItems(Page fc_page, int *fc_nitems, ItemPointerData fc_advancePast)
{
	ItemPointer fc_result;

	if (GinPageIsCompressed(fc_page))
	{
		GinPostingList *fc_seg = GinDataLeafPageGetPostingList(fc_page);
		Size		fc_len = GinDataLeafPageGetPostingListSize(fc_page);
		Pointer		fc_endptr = ((Pointer) fc_seg) + fc_len;
		GinPostingList *fc_next;

		/* 跳过到包含advancePast+1的段 */
		if (ItemPointerIsValid(&fc_advancePast))
		{
			fc_next = GinNextPostingListSegment(fc_seg);
			while ((Pointer) fc_next < fc_endptr &&
				   ginCompareItemPointers(&fc_next->first, &fc_advancePast) <= 0)
			{
				fc_seg = fc_next;
				fc_next = GinNextPostingListSegment(fc_seg);
			}
			fc_len = fc_endptr - (Pointer) fc_seg;
		}

		if (fc_len > 0)
			fc_result = ginPostingListDecodeAllSegments(fc_seg, fc_len, fc_nitems);
		else
		{
			fc_result = NULL;
			*fc_nitems = 0;
		}
	}
	else
	{
		ItemPointer fc_tmp = fc_dataLeafPageGetUncompressed(fc_page, fc_nitems);

		fc_result = palloc((*fc_nitems) * sizeof(ItemPointerData));
		memcpy(fc_result, fc_tmp, (*fc_nitems) * sizeof(ItemPointerData));
	}

	return fc_result;
}

/*
 * 将所有TIDs从叶子数据页面放入位图中。
 */
int GinDataLeafPageGetItemsToTbm(Page fc_page, TIDBitmap *fc_tbm)
{
	ItemPointer fc_uncompressed;
	int			fc_nitems;

	if (GinPageIsCompressed(fc_page))
	{
		GinPostingList *fc_segment = GinDataLeafPageGetPostingList(fc_page);
		Size		fc_len = GinDataLeafPageGetPostingListSize(fc_page);

		fc_nitems = ginPostingListDecodeAllSegmentsToTbm(fc_segment, fc_len, fc_tbm);
	}
	else
	{
		fc_uncompressed = fc_dataLeafPageGetUncompressed(fc_page, &fc_nitems);

		if (fc_nitems > 0)
			tbm_add_tuples(fc_tbm, fc_uncompressed, fc_nitems, false);
	}

	return fc_nitems;
}

/*
 * 获取指向未压缩项数组的指针，在预9.4格式的未压缩叶子页面上。
 * 数组中的项数通过*nitems返回。
 */
static ItemPointer fc_dataLeafPageGetUncompressed(Page fc_page, int *fc_nitems)
{
	ItemPointer fc_items;

	Assert(!GinPageIsCompressed(fc_page));

	/*
	 * 在旧的预9.4页面格式中，整个页面内容用于未压缩项，
	 * 项数存储在'maxoff'中。
	 */
	fc_items = (ItemPointer) GinDataPageGetData(fc_page);
	*fc_nitems = GinPageGetOpaque(fc_page)->maxoff;

	return fc_items;
}

/*
 * 检查我们是否应该跟随右链接以找到我们正在搜索的项。
 *
 * 将插入项指针与当前页面的右边界进行比较。
 */
static bool fc_dataIsMoveRight(GinBtree fc_btree, Page fc_page)
{
	ItemPointer fc_iptr = GinDataPageGetRightBound(fc_page);

	if (GinPageRightMost(fc_page))
		return false;

	if (GinPageIsDeleted(fc_page))
		return true;

	return (ginCompareItemPointers(&fc_btree->itemptr, fc_iptr) > 0);
}

/*
 * 在非叶子页面中找到正确的PostingItem。假设这是
 * 正确的页面，搜索的值应该在该页面上。
 */
static BlockNumber fc_dataLocateItem(GinBtree fc_btree, GinBtreeStack *fc_stack)
{
	OffsetNumber fc_low,
				fc_high,
				fc_maxoff;
	PostingItem *fc_pitem = NULL;
	int			fc_result;
	Page		fc_page = BufferGetPage(fc_stack->buffer);

	Assert(!GinPageIsLeaf(fc_page));
	Assert(GinPageIsData(fc_page));

	if (fc_btree->fullScan)
	{
		fc_stack->off = FirstOffsetNumber;
		fc_stack->predictNumber *= GinPageGetOpaque(fc_page)->maxoff;
		return fc_btree->getLeftMostChild(fc_btree, fc_page);
	}

	fc_low = FirstOffsetNumber;
	fc_maxoff = fc_high = GinPageGetOpaque(fc_page)->maxoff;
	Assert(fc_high >= fc_low);

	fc_high++;

	while (fc_high > fc_low)
	{
		OffsetNumber fc_mid = fc_low + ((fc_high - fc_low) / 2);

		fc_pitem = GinDataPageGetPostingItem(fc_page, fc_mid);

		if (fc_mid == fc_maxoff)
		{
			/*
			 * 右无穷大，页面已经通过
			 * dataIsMoveRight正确选择。
			 */
			fc_result = -1;
		}
		else
		{
			fc_pitem = GinDataPageGetPostingItem(fc_page, fc_mid);
			fc_result = ginCompareItemPointers(&fc_btree->itemptr, &(fc_pitem->key));
		}

		if (fc_result == 0)
		{
			fc_stack->off = fc_mid;
			return PostingItemGetBlockNumber(fc_pitem);
		}
		else if (fc_result > 0)
			fc_low = fc_mid + 1;
		else
			fc_high = fc_mid;
	}

	Assert(fc_high >= FirstOffsetNumber && fc_high <= fc_maxoff);

	fc_stack->off = fc_high;
	fc_pitem = GinDataPageGetPostingItem(fc_page, fc_high);
	return PostingItemGetBlockNumber(fc_pitem);
}

/*
 * 在非叶子页面上找到blkno的链接，返回PostingItem的偏移量。
 */
static OffsetNumber fc_dataFindChildPtr(GinBtree fc_btree, Page fc_page, BlockNumber fc_blkno, OffsetNumber fc_storedOff)
{
	OffsetNumber fc_i,
				fc_maxoff = GinPageGetOpaque(fc_page)->maxoff;
	PostingItem *fc_pitem;

	Assert(!GinPageIsLeaf(fc_page));
	Assert(GinPageIsData(fc_page));

	/* 如果页面没有改变，我们返回存储的偏移量 */
	if (fc_storedOff >= FirstOffsetNumber && fc_storedOff <= fc_maxoff)
	{
		fc_pitem = GinDataPageGetPostingItem(fc_page, fc_storedOff);
		if (PostingItemGetBlockNumber(fc_pitem) == fc_blkno)
			return fc_storedOff;

		/*
		 * 我们希望所需指针向右移动。如果没有删除，这是真的。
		 */
		for (fc_i = fc_storedOff + 1; fc_i <= fc_maxoff; fc_i++)
		{
			fc_pitem = GinDataPageGetPostingItem(fc_page, fc_i);
			if (PostingItemGetBlockNumber(fc_pitem) == fc_blkno)
				return fc_i;
		}

		fc_maxoff = fc_storedOff - 1;
	}

	/* 最后机会 */
	for (fc_i = FirstOffsetNumber; fc_i <= fc_maxoff; fc_i++)
	{
		fc_pitem = GinDataPageGetPostingItem(fc_page, fc_i);
		if (PostingItemGetBlockNumber(fc_pitem) == fc_blkno)
			return fc_i;
	}

	return InvalidOffsetNumber;
}

/*
 * 返回最左子节点的blkno。
 */
static BlockNumber fc_dataGetLeftMostPage(GinBtree fc_btree, Page fc_page)
{
	PostingItem *fc_pitem;

	Assert(!GinPageIsLeaf(fc_page));
	Assert(GinPageIsData(fc_page));
	Assert(GinPageGetOpaque(fc_page)->maxoff >= FirstOffsetNumber);

	fc_pitem = GinDataPageGetPostingItem(fc_page, FirstOffsetNumber);
	return PostingItemGetBlockNumber(fc_pitem);
}

/*
 * 将PostingItem添加到非叶子页面。
 */
void GinDataPageAddPostingItem(Page fc_page, PostingItem *fc_data, OffsetNumber fc_offset)
{
	OffsetNumber fc_maxoff = GinPageGetOpaque(fc_page)->maxoff;
	char	   *fc_ptr;

	Assert(PostingItemGetBlockNumber(fc_data) != InvalidBlockNumber);
	Assert(!GinPageIsLeaf(fc_page));

	if (fc_offset == InvalidOffsetNumber)
	{
		fc_ptr = (char *) GinDataPageGetPostingItem(fc_page, fc_maxoff + 1);
	}
	else
	{
		fc_ptr = (char *) GinDataPageGetPostingItem(fc_page, fc_offset);
		if (fc_offset != fc_maxoff + 1)
			memmove(fc_ptr + sizeof(PostingItem),
					fc_ptr,
					(fc_maxoff - fc_offset + 1) * sizeof(PostingItem));
	}
	memcpy(fc_ptr, fc_data, sizeof(PostingItem));

	fc_maxoff++;
	GinPageGetOpaque(fc_page)->maxoff = fc_maxoff;

	/*
	 * 还将pd_lower设置为发布项的末尾，以遵循
	 * “标准”页面布局，以便我们可以挤出完整页面图像的未使用空间。
	 */
	GinDataPageSetDataSize(fc_page, fc_maxoff * sizeof(PostingItem));
}

/*
 * 从非叶子页面中删除发布项。
 */
void GinPageDeletePostingItem(Page fc_page, OffsetNumber fc_offset)
{
	OffsetNumber fc_maxoff = GinPageGetOpaque(fc_page)->maxoff;

	Assert(!GinPageIsLeaf(fc_page));
	Assert(fc_offset >= FirstOffsetNumber && fc_offset <= fc_maxoff);

	if (fc_offset != fc_maxoff)
		memmove(GinDataPageGetPostingItem(fc_page, fc_offset),
				GinDataPageGetPostingItem(fc_page, fc_offset + 1),
				sizeof(PostingItem) * (fc_maxoff - fc_offset));

	fc_maxoff--;
	GinPageGetOpaque(fc_page)->maxoff = fc_maxoff;

	GinDataPageSetDataSize(fc_page, fc_maxoff * sizeof(PostingItem));
}

/*
 * 准备在叶子数据页面上插入数据。
 *
 * 如果可以容纳，返回GPTP_INSERT，在进入插入关键区段之前执行任何所需的设置。
 *ptp_workspace可以设置以将信息传递给execPlaceToPage函数。
 *
 * 如果无法容纳，执行页面拆分，并将两个临时页面
 * 图像返回到*newlpage和*newrpage，结果为GPTP_SPLIT。
 *
 * 在两种情况下，给定的页面缓冲区都不应在此处修改。
 */
static GinPlaceToPageRC fc_dataBeginPlaceToPageLeaf(GinBtree fc_btree, Buffer fc_buf, GinBtreeStack *fc_stack,
						 void *fc_insertdata,
						 void **fc_ptp_workspace,
						 Page *fc_newlpage, Page *fc_newrpage)
{
	GinBtreeDataLeafInsertData *fc_items = fc_insertdata;
	ItemPointer fc_newItems = &fc_items->items[fc_items->curitem];
	int			fc_maxitems = fc_items->nitem - fc_items->curitem;
	Page		fc_page = BufferGetPage(fc_buf);
	int			fc_i;
	ItemPointerData fc_rbound;
	ItemPointerData fc_lbound;
	bool		fc_needsplit;
	bool		fc_append;
	int			fc_segsize;
	Size		fc_freespace;
	disassembledLeaf *fc_leaf;
	leafSegmentInfo *fc_lastleftinfo;
	ItemPointerData fc_maxOldItem;
	ItemPointerData fc_remaining;

	fc_rbound = *GinDataPageGetRightBound(fc_page);

	/*
	 * 统计有多少新项属于此页面。
	 */
	if (!GinPageRightMost(fc_page))
	{
		for (fc_i = 0; fc_i < fc_maxitems; fc_i++)
		{
			if (ginCompareItemPointers(&fc_newItems[fc_i], &fc_rbound) > 0)
			{
				/*
				 * 这需要转到树中的其他位置。(调用者应该选择插入位置，
				 * 这样至少第一个项就会在这里。)
				 */
				Assert(fc_i > 0);
				break;
			}
		}
		fc_maxitems = fc_i;
	}

	/* 拆分页面上的数据 */
	fc_leaf = fc_disassembleLeaf(fc_page);

	/*
	 * 我们是在向页面的末尾追加吗？换句话说，所有新项
	 * 是否都大于任何现有项。
	 */
	if (!dlist_is_empty(&fc_leaf->segments))
	{
		fc_lastleftinfo = dlist_container(leafSegmentInfo, node,
									   dlist_tail_node(&fc_leaf->segments));
		if (!fc_lastleftinfo->items)
			fc_lastleftinfo->items = ginPostingListDecode(fc_lastleftinfo->seg,
													   &fc_lastleftinfo->nitems);
		fc_maxOldItem = fc_lastleftinfo->items[fc_lastleftinfo->nitems - 1];
		if (ginCompareItemPointers(&fc_newItems[0], &fc_maxOldItem) >= 0)
			fc_append = true;
		else
			fc_append = false;
	}
	else
	{
		ItemPointerSetMin(&fc_maxOldItem);
		fc_append = true;
	}

	/*
	 * 如果我们是在向页面的末尾追加，我们将追加尽可能多的项
	 * （拆分后），并在页面变满时停止。
	 * 否则，我们必须限制要插入的新项数量，因为
	 * 一旦开始打包，我们不能在空间用尽时停止，
	 * 因为我们必须确保所有旧项仍然适合。
	 */
	if (GinPageIsCompressed(fc_page))
		fc_freespace = GinDataLeafPageGetFreeSpace(fc_page);
	else
		fc_freespace = 0;
	if (fc_append)
	{
		/*
		 * 即使在追加时，尝试追加超过适合的项也是不完全免费的，因为我们将在下面将新项和旧项合并到一个数组中。在最好的情况下，每个新项占用一个字节，我们可以利用旧页面和新页面的所有空闲空间。为简单起见，忽略段开销等。
		 */
		fc_maxitems = Min(fc_maxitems, fc_freespace + GinDataPageMaxDataSize);
	}
	else
	{
		/*
		 * 计算在拆分后两个页面上可以容纳多少个新项的保守估计。
		 *
		 * 我们可以利用旧页面上任何剩余的空闲空间来存储完整段，以及新页面。每个全尺寸段至少可以容纳 MinTuplesPerSegment 项。
		 */
		int			fc_nnewsegments;

		fc_nnewsegments = fc_freespace / GinPostingListSegmentMaxSize;
		fc_nnewsegments += GinDataPageMaxDataSize / GinPostingListSegmentMaxSize;
		fc_maxitems = Min(fc_maxitems, fc_nnewsegments * MinTuplesPerSegment);
	}

	/* 将新项添加到段列表 */
	if (!fc_addItemsToLeaf(fc_leaf, fc_newItems, fc_maxitems))
	{
		/* 所有项都是重复项，我们没有工作要做 */
		fc_items->curitem += fc_maxitems;

		return GPTP_NO_WORK;
	}

	/*
	 * 将项打包回压缩段，准备写入磁盘。
	 */
	fc_needsplit = fc_leafRepackItems(fc_leaf, &fc_remaining);

	/*
	 * 所有新项都适合吗？
	 *
	 * 如果我们在追加，那没有关系。但作为一种理智检查，验证所有旧项是否适合。
	 */
	if (ItemPointerIsValid(&fc_remaining))
	{
		if (!fc_append || ItemPointerCompare(&fc_maxOldItem, &fc_remaining) >= 0)
			elog(ERROR, "could not split GIN page; all old items didn't fit");

		/* 统计适合的新项数量。 */
		for (fc_i = 0; fc_i < fc_maxitems; fc_i++)
		{
			if (ginCompareItemPointers(&fc_newItems[fc_i], &fc_remaining) >= 0)
				break;
		}
		if (fc_i == 0)
			elog(ERROR, "could not split GIN page; no new items fit");
		fc_maxitems = fc_i;
	}

	if (!fc_needsplit)
	{
		/*
		 * 太好了，所有项都适合一个页面。如果需要，准备描述我们将要做的更改的数据以用于 WAL 记录。
		 */
		if (RelationNeedsWAL(fc_btree->index) && !fc_btree->isBuild)
			fc_computeLeafRecompressWALData(fc_leaf);

		/*
		 * 我们准备进入关键部分，但
		 * dataExecPlaceToPageLeaf 需要访问 "leaf" 数据。
		 */
		*fc_ptp_workspace = fc_leaf;

		if (fc_append)
			elog(DEBUG2, "appended %d new items to block %u; %d bytes (%d to go)",
				 fc_maxitems, BufferGetBlockNumber(fc_buf), (int) fc_leaf->lsize,
				 fc_items->nitem - fc_items->curitem - fc_maxitems);
		else
			elog(DEBUG2, "inserted %d new items to block %u; %d bytes (%d to go)",
				 fc_maxitems, BufferGetBlockNumber(fc_buf), (int) fc_leaf->lsize,
				 fc_items->nitem - fc_items->curitem - fc_maxitems);
	}
	else
	{
		/*
		 * 必须拆分。
		 *
		 * leafRepackItems 已经在左页面和右页面之间划分了段。它尽可能填满左页面，并将其余部分放入右页面。在构建新索引时，这是好的，因为表是从头到尾扫描的，并且在构建过程中不会再向左页面插入任何内容。这使索引尽可能紧凑。否则，以 50/50 的方式拆分，通过将段从左页面移动到右页面直到它们平衡。
		 *
		 * 作为进一步的启发式，当向页面末尾追加项时，尝试使左页面达到 75% 的满度，假设后续插入也可能进入末尾。这在向表追加时使索引更加紧凑，这是非常常见的。
		 */
		if (!fc_btree->isBuild)
		{
			while (dlist_has_prev(&fc_leaf->segments, fc_leaf->lastleft))
			{
				fc_lastleftinfo = dlist_container(leafSegmentInfo, node, fc_leaf->lastleft);

				/* 忽略已删除的段 */
				if (fc_lastleftinfo->action != GIN_SEGMENT_DELETE)
				{
					fc_segsize = SizeOfGinPostingList(fc_lastleftinfo->seg);

					/*
					 * 请注意，即使在追加时，我们也会检查右页面是否不会比左页面更满。可能我们添加了足够的项，使得两个页面都超过了 75% 的满度。
					 */
					if ((fc_leaf->lsize - fc_segsize) - (fc_leaf->rsize + fc_segsize) < 0)
						break;
					if (fc_append)
					{
						if ((fc_leaf->lsize - fc_segsize) < (BLCKSZ * 3) / 4)
							break;
					}

					fc_leaf->lsize -= fc_segsize;
					fc_leaf->rsize += fc_segsize;
				}
				fc_leaf->lastleft = dlist_prev_node(&fc_leaf->segments, fc_leaf->lastleft);
			}
		}
		Assert(fc_leaf->lsize <= GinDataPageMaxDataSize);
		Assert(fc_leaf->rsize <= GinDataPageMaxDataSize);

		/*
		 * 获取左页面最后一段中的最大项；它成为页面的右边界。
		 */
		fc_lastleftinfo = dlist_container(leafSegmentInfo, node, fc_leaf->lastleft);
		if (!fc_lastleftinfo->items)
			fc_lastleftinfo->items = ginPostingListDecode(fc_lastleftinfo->seg,
													   &fc_lastleftinfo->nitems);
		fc_lbound = fc_lastleftinfo->items[fc_lastleftinfo->nitems - 1];

		/*
		 * 现在分配几个临时页面图像，并填充它们。
		 */
		*fc_newlpage = palloc(BLCKSZ);
		*fc_newrpage = palloc(BLCKSZ);

		fc_dataPlaceToPageLeafSplit(fc_leaf, fc_lbound, fc_rbound,
								 *fc_newlpage, *fc_newrpage);

		Assert(GinPageRightMost(fc_page) ||
			   ginCompareItemPointers(GinDataPageGetRightBound(*fc_newlpage),
									  GinDataPageGetRightBound(*fc_newrpage)) < 0);

		if (fc_append)
			elog(DEBUG2, "appended %d items to block %u; split %d/%d (%d to go)",
				 fc_maxitems, BufferGetBlockNumber(fc_buf), (int) fc_leaf->lsize, (int) fc_leaf->rsize,
				 fc_items->nitem - fc_items->curitem - fc_maxitems);
		else
			elog(DEBUG2, "inserted %d items to block %u; split %d/%d (%d to go)",
				 fc_maxitems, BufferGetBlockNumber(fc_buf), (int) fc_leaf->lsize, (int) fc_leaf->rsize,
				 fc_items->nitem - fc_items->curitem - fc_maxitems);
	}

	fc_items->curitem += fc_maxitems;

	return fc_needsplit ? GPTP_SPLIT : GPTP_INSERT;
}

/*
 * 在 beginPlaceToPage 决定它会适合后执行数据插入。
 *
 * 这是在关键部分内部调用的，XLOG 记录创建（如果需要）已经开始。目标缓冲区在槽 0 中注册。
 */
static void fc_dataExecPlaceToPageLeaf(GinBtree fc_btree, Buffer fc_buf, GinBtreeStack *fc_stack,
						void *fc_insertdata, void *fc_ptp_workspace)
{
	disassembledLeaf *fc_leaf = (disassembledLeaf *) fc_ptp_workspace;

	/* 将更改应用到页面 */
	fc_dataPlaceToPageLeafRecompress(fc_buf, fc_leaf);

	/* 如果需要，由 computeLeafRecompressWALData 构建的 WAL 数据进行注册 */
	if (RelationNeedsWAL(fc_btree->index) && !fc_btree->isBuild)
	{
		XLogRegisterBufData(0, fc_leaf->walinfo, fc_leaf->walinfolen);
	}
}

/*
 * 清理一个发布树叶页面。
 */
void ginVacuumPostingTreeLeaf(Relation fc_indexrel, Buffer fc_buffer, GinVacuumState *fc_gvs)
{
	Page		fc_page = BufferGetPage(fc_buffer);
	disassembledLeaf *fc_leaf;
	bool		fc_removedsomething = false;
	dlist_iter	fc_iter;

	fc_leaf = fc_disassembleLeaf(fc_page);

	/* 清理每个段。 */
	dlist_foreach(fc_iter, &fc_leaf->segments)
	{
		leafSegmentInfo *fc_seginfo = dlist_container(leafSegmentInfo, node, fc_iter.cur);
		int			fc_oldsegsize;
		ItemPointer fc_cleaned;
		int			fc_ncleaned;

		if (!fc_seginfo->items)
			fc_seginfo->items = ginPostingListDecode(fc_seginfo->seg,
												  &fc_seginfo->nitems);
		if (fc_seginfo->seg)
			fc_oldsegsize = SizeOfGinPostingList(fc_seginfo->seg);
		else
			fc_oldsegsize = GinDataPageMaxDataSize;

		fc_cleaned = ginVacuumItemPointers(fc_gvs,
										fc_seginfo->items,
										fc_seginfo->nitems,
										&fc_ncleaned);
		pfree(fc_seginfo->items);
		fc_seginfo->items = NULL;
		fc_seginfo->nitems = 0;
		if (fc_cleaned)
		{
			if (fc_ncleaned > 0)
			{
				int			fc_npacked;

				fc_seginfo->seg = ginCompressPostingList(fc_cleaned,
													  fc_ncleaned,
													  fc_oldsegsize,
													  &fc_npacked);
				/* 删除项目从未增加段的大小 */
				if (fc_npacked != fc_ncleaned)
					elog(ERROR, "could not fit vacuumed posting list");
				fc_seginfo->action = GIN_SEGMENT_REPLACE;
			}
			else
			{
				fc_seginfo->seg = NULL;
				fc_seginfo->items = NULL;
				fc_seginfo->action = GIN_SEGMENT_DELETE;
			}
			fc_seginfo->nitems = fc_ncleaned;

			fc_removedsomething = true;
		}
	}

	/*
	 * 如果我们删除了任何项目，从碎片中重建页面。
	 *
	 * 尽管我们删除了一些项目后，有些段可能变得很小，但我们
	 * 不会尝试在此重新编码段。这似乎是浪费精力，因为
	 * 较大的段本身并没有什么好处；较大的段只是有助于在
	 * 相同的空间中打包更多项目。我们可以推迟到下一个
	 * 插入时再进行这项操作，因为无论如何这将需要
	 * 重新编码页面的至少部分。
	 *
	 * 还要注意，如果页面之前处于未压缩的 9.4 之前格式，
	 * 那么现在它被表示为一个包含所有项目的巨大段。
	 * 将其拆分以加快随机访问可能是有意义的，但我们不
	 * 想麻烦。无论如何，如果您想获得新更紧凑的索引
	 * 格式的全部收益，您将不得不进行重新索引。
	 */
	if (fc_removedsomething)
	{
		bool		fc_modified;

		/*
		 * 确保在修改的第一个段之后，我们对所有段有一个 palloc 的副本。
		 * (dataPlaceToPageLeafRecompress 需要这样做)。
		 */
		fc_modified = false;
		dlist_foreach(fc_iter, &fc_leaf->segments)
		{
			leafSegmentInfo *fc_seginfo = dlist_container(leafSegmentInfo, node,
													   fc_iter.cur);

			if (fc_seginfo->action != GIN_SEGMENT_UNMODIFIED)
				fc_modified = true;
			if (fc_modified && fc_seginfo->action != GIN_SEGMENT_DELETE)
			{
				int			fc_segsize = SizeOfGinPostingList(fc_seginfo->seg);
				GinPostingList *fc_tmp = (GinPostingList *) palloc(fc_segsize);

				memcpy(fc_tmp, fc_seginfo->seg, fc_segsize);
				fc_seginfo->seg = fc_tmp;
			}
		}

		if (RelationNeedsWAL(fc_indexrel))
			fc_computeLeafRecompressWALData(fc_leaf);

		/* 将更改应用到页面 */
		START_CRIT_SECTION();

		fc_dataPlaceToPageLeafRecompress(fc_buffer, fc_leaf);

		MarkBufferDirty(fc_buffer);

		if (RelationNeedsWAL(fc_indexrel))
		{
			XLogRecPtr	fc_recptr;

			XLogBeginInsert();
			XLogRegisterBuffer(0, fc_buffer, REGBUF_STANDARD);
			XLogRegisterBufData(0, fc_leaf->walinfo, fc_leaf->walinfolen);
			fc_recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_VACUUM_DATA_LEAF_PAGE);
			PageSetLSN(fc_page, fc_recptr);
		}

		END_CRIT_SECTION();
	}
}

/*
 * 构建一个 ginxlogRecompressDataLeaf 记录，表示 *leaf 中
 * 的更改。 (因为这需要 palloc，我们必须在进入实际更新页面的
 * 临界区之前进行此操作。)
 */
static void fc_computeLeafRecompressWALData(disassembledLeaf *fc_leaf)
{
	int			fc_nmodified = 0;
	char	   *fc_walbufbegin;
	char	   *fc_walbufend;
	dlist_iter	fc_iter;
	int			fc_segno;
	ginxlogRecompressDataLeaf *fc_recompress_xlog;

	/* 计算已修改的段 */
	dlist_foreach(fc_iter, &fc_leaf->segments)
	{
		leafSegmentInfo *fc_seginfo = dlist_container(leafSegmentInfo, node,
												   fc_iter.cur);

		if (fc_seginfo->action != GIN_SEGMENT_UNMODIFIED)
			fc_nmodified++;
	}

	fc_walbufbegin =
		palloc(sizeof(ginxlogRecompressDataLeaf) +
			   BLCKSZ +			/* 存储段数据所需的最大大小 */
			   fc_nmodified * 2	/* 每个操作的 (segno + action) */
		);
	fc_walbufend = fc_walbufbegin;

	fc_recompress_xlog = (ginxlogRecompressDataLeaf *) fc_walbufend;
	fc_walbufend += sizeof(ginxlogRecompressDataLeaf);

	fc_recompress_xlog->nactions = fc_nmodified;

	fc_segno = 0;
	dlist_foreach(fc_iter, &fc_leaf->segments)
	{
		leafSegmentInfo *fc_seginfo = dlist_container(leafSegmentInfo, node,
												   fc_iter.cur);
		int			fc_segsize = 0;
		int			fc_datalen;
		uint8		fc_action = fc_seginfo->action;

		if (fc_action == GIN_SEGMENT_UNMODIFIED)
		{
			fc_segno++;
			continue;
		}

		if (fc_action != GIN_SEGMENT_DELETE)
			fc_segsize = SizeOfGinPostingList(fc_seginfo->seg);

		/*
		 * 如果存储未压缩的新增项目指针列表所需的空间
		 * 比存储压缩段所需的空间还多，则改为进行此操作。
		 */
		if (fc_action == GIN_SEGMENT_ADDITEMS &&
			fc_seginfo->nmodifieditems * sizeof(ItemPointerData) > fc_segsize)
		{
			fc_action = GIN_SEGMENT_REPLACE;
		}

		*((uint8 *) (fc_walbufend++)) = fc_segno;
		*(fc_walbufend++) = fc_action;

		switch (fc_action)
		{
			case GIN_SEGMENT_DELETE:
				fc_datalen = 0;
				break;

			case GIN_SEGMENT_ADDITEMS:
				fc_datalen = fc_seginfo->nmodifieditems * sizeof(ItemPointerData);
				memcpy(fc_walbufend, &fc_seginfo->nmodifieditems, sizeof(uint16));
				memcpy(fc_walbufend + sizeof(uint16), fc_seginfo->modifieditems, fc_datalen);
				fc_datalen += sizeof(uint16);
				break;

			case GIN_SEGMENT_INSERT:
			case GIN_SEGMENT_REPLACE:
				fc_datalen = SHORTALIGN(fc_segsize);
				memcpy(fc_walbufend, fc_seginfo->seg, fc_segsize);
				break;

			default:
				elog(ERROR, "unexpected GIN leaf action %d", fc_action);
		}
		fc_walbufend += fc_datalen;

		if (fc_action != GIN_SEGMENT_INSERT)
			fc_segno++;
	}

	/* 通过 *leaf 返回构建的信息 */
	fc_leaf->walinfo = fc_walbufbegin;
	fc_leaf->walinfolen = fc_walbufend - fc_walbufbegin;
}

/*
 * 将分解的发布树叶页面组装回缓冲区。
 *
 * 这只是更新目标缓冲区；WAL 的内容由调用者负责。
 *
 * 注意：段指针不得直接指向同一个缓冲区，
 * 除非这些段没有被修改，且其前面的段也没有被修改。
 */
static void fc_dataPlaceToPageLeafRecompress(Buffer fc_buf, disassembledLeaf *fc_leaf)
{
	Page		fc_page = BufferGetPage(fc_buf);
	char	   *fc_ptr;
	int			fc_newsize;
	bool		fc_modified = false;
	dlist_iter	fc_iter;
	int			fc_segsize;

	/*
	 * 如果页面之前处于 9.4 之前格式，则转换头部，并强制
	 * 所有段无论是否被修改，都复制到页面。
	 */
	if (!GinPageIsCompressed(fc_page))
	{
		Assert(fc_leaf->oldformat);
		GinPageSetCompressed(fc_page);
		GinPageGetOpaque(fc_page)->maxoff = InvalidOffsetNumber;
		fc_modified = true;
	}

	fc_ptr = (char *) GinDataLeafPageGetPostingList(fc_page);
	fc_newsize = 0;
	dlist_foreach(fc_iter, &fc_leaf->segments)
	{
		leafSegmentInfo *fc_seginfo = dlist_container(leafSegmentInfo, node, fc_iter.cur);

		if (fc_seginfo->action != GIN_SEGMENT_UNMODIFIED)
			fc_modified = true;

		if (fc_seginfo->action != GIN_SEGMENT_DELETE)
		{
			fc_segsize = SizeOfGinPostingList(fc_seginfo->seg);

			if (fc_modified)
				memcpy(fc_ptr, fc_seginfo->seg, fc_segsize);

			fc_ptr += fc_segsize;
			fc_newsize += fc_segsize;
		}
	}

	Assert(fc_newsize <= GinDataPageMaxDataSize);
	GinDataPageSetDataSize(fc_page, fc_newsize);
}

/*
 * 类似于 dataPlaceToPageLeafRecompress，但将分解的叶
 * 段写入两个页面，而不是一个。
 *
 * 这与非拆分情况不同，因为这并不直接修改
 * 原始页面，而是写入新的左页面和右页面的临时内存副本。
 */
static void fc_dataPlaceToPageLeafSplit(disassembledLeaf *fc_leaf,
						 ItemPointerData fc_lbound, ItemPointerData fc_rbound,
						 Page fc_lpage, Page fc_rpage)
{
	char	   *fc_ptr;
	int			fc_segsize;
	int			fc_lsize;
	int			fc_rsize;
	dlist_node *fc_node;
	dlist_node *fc_firstright;
	leafSegmentInfo *fc_seginfo;

	/* 初始化临时页面以容纳新的左页面和右页面 */
	GinInitPage(fc_lpage, GIN_DATA | GIN_LEAF | GIN_COMPRESSED, BLCKSZ);
	GinInitPage(fc_rpage, GIN_DATA | GIN_LEAF | GIN_COMPRESSED, BLCKSZ);

	/*
	 * 复制前往左页面的段。
	 *
	 * XXX：我们应该跳过复制未修改的左页面部分，
	 * 就像我们在重新压缩时那样。
	 */
	fc_lsize = 0;
	fc_ptr = (char *) GinDataLeafPageGetPostingList(fc_lpage);
	fc_firstright = dlist_next_node(&fc_leaf->segments, fc_leaf->lastleft);
	for (fc_node = dlist_head_node(&fc_leaf->segments);
		 fc_node != fc_firstright;
		 fc_node = dlist_next_node(&fc_leaf->segments, fc_node))
	{
		fc_seginfo = dlist_container(leafSegmentInfo, node, fc_node);

		if (fc_seginfo->action != GIN_SEGMENT_DELETE)
		{
			fc_segsize = SizeOfGinPostingList(fc_seginfo->seg);
			memcpy(fc_ptr, fc_seginfo->seg, fc_segsize);
			fc_ptr += fc_segsize;
			fc_lsize += fc_segsize;
		}
	}
	Assert(fc_lsize == fc_leaf->lsize);
	GinDataPageSetDataSize(fc_lpage, fc_lsize);
	*GinDataPageGetRightBound(fc_lpage) = fc_lbound;

	/* 复制前往右页面的段 */
	fc_ptr = (char *) GinDataLeafPageGetPostingList(fc_rpage);
	fc_rsize = 0;
	for (fc_node = fc_firstright;
		 ;
		 fc_node = dlist_next_node(&fc_leaf->segments, fc_node))
	{
		fc_seginfo = dlist_container(leafSegmentInfo, node, fc_node);

		if (fc_seginfo->action != GIN_SEGMENT_DELETE)
		{
			fc_segsize = SizeOfGinPostingList(fc_seginfo->seg);
			memcpy(fc_ptr, fc_seginfo->seg, fc_segsize);
			fc_ptr += fc_segsize;
			fc_rsize += fc_segsize;
		}

		if (!dlist_has_next(&fc_leaf->segments, fc_node))
			break;
	}
	Assert(fc_rsize == fc_leaf->rsize);
	GinDataPageSetDataSize(fc_rpage, fc_rsize);
	*GinDataPageGetRightBound(fc_rpage) = fc_rbound;
}

/*
 * 准备在内部数据页上插入数据。
 *
 * 如果可以容纳，则在进入插入临界区之前执行所需的任何设置后，返回 GPTP_INSERT。*ptp_workspace 可以设置以将信息传递给 execPlaceToPage 函数。
 *
 * 如果不能容纳，则执行页面拆分并将两个临时页面图像返回到 *newlpage 和 *newrpage，结果为 GPTP_SPLIT。
 *
 * 在这两种情况下，都不应在此修改给定的页面缓冲区。
 *
 * 注意：在插入到内部节点时，除了插入给定项外，还将更新位于 stack->off 的现有项的下行链接，以指向 updateblkno。
 */
static GinPlaceToPageRC fc_dataBeginPlaceToPageInternal(GinBtree fc_btree, Buffer fc_buf, GinBtreeStack *fc_stack,
							 void *fc_insertdata, BlockNumber fc_updateblkno,
							 void **fc_ptp_workspace,
							 Page *fc_newlpage, Page *fc_newrpage)
{
	Page		fc_page = BufferGetPage(fc_buf);

	/* 如果不能容纳，处理拆分情况 */
	if (GinNonLeafDataPageGetFreeSpace(fc_page) < sizeof(PostingItem))
	{
		fc_dataSplitPageInternal(fc_btree, fc_buf, fc_stack, fc_insertdata, fc_updateblkno,
							  fc_newlpage, fc_newrpage);
		return GPTP_SPLIT;
	}

	/* 否则，我们准备继续插入 */
	return GPTP_INSERT;
}

/*
 * 在 beginPlaceToPage 决定它会适合后执行数据插入。
 *
 * 这是在关键部分内部调用的，XLOG 记录创建（如果需要）已经开始。目标缓冲区在槽 0 中注册。
 */
static void fc_dataExecPlaceToPageInternal(GinBtree fc_btree, Buffer fc_buf, GinBtreeStack *fc_stack,
							void *fc_insertdata, BlockNumber fc_updateblkno,
							void *fc_ptp_workspace)
{
	Page		fc_page = BufferGetPage(fc_buf);
	OffsetNumber fc_off = fc_stack->off;
	PostingItem *fc_pitem;

	/* 更新现有的下行链接以指向下一页（在内部页面上） */
	fc_pitem = GinDataPageGetPostingItem(fc_page, fc_off);
	PostingItemSetBlockNumber(fc_pitem, fc_updateblkno);

	/* 添加新项 */
	fc_pitem = (PostingItem *) fc_insertdata;
	GinDataPageAddPostingItem(fc_page, fc_pitem, fc_off);

	if (RelationNeedsWAL(fc_btree->index) && !fc_btree->isBuild)
	{
		/*
		 * 这必须是静态的，因为它必须在 XLogInsert 之前存活，
		 * 而我们不能在此调用 palloc。虽然不太优雅，但 XLogInsert 的基础设施
		 * 本来就不是可重入的。
		 */
		static ginxlogInsertDataInternal fc_data;

		fc_data.offset = fc_off;
		fc_data.newitem = *fc_pitem;

		XLogRegisterBufData(0, (char *) &fc_data,
							sizeof(ginxlogInsertDataInternal));
	}
}

/*
 * 准备在发布树数据页上插入数据。
 *
 * 如果可以容纳，则在进入插入临界区之前执行所需的任何设置后，返回 GPTP_INSERT。*ptp_workspace 可以设置以将信息传递给 execPlaceToPage 函数。
 *
 * 如果不能容纳，则执行页面拆分并将两个临时页面图像返回到 *newlpage 和 *newrpage，结果为 GPTP_SPLIT。
 *
 * 在这两种情况下，都不应在此修改给定的页面缓冲区。
 *
 * 注意：在插入到内部节点时，除了插入给定项外，还将更新位于 stack->off 的现有项的下行链接，以指向 updateblkno。
 *
 * 调用内部或叶子页面的相关函数，因为它们的处理方式非常不同。
 */
static GinPlaceToPageRC fc_dataBeginPlaceToPage(GinBtree fc_btree, Buffer fc_buf, GinBtreeStack *fc_stack,
					 void *fc_insertdata, BlockNumber fc_updateblkno,
					 void **fc_ptp_workspace,
					 Page *fc_newlpage, Page *fc_newrpage)
{
	Page		fc_page = BufferGetPage(fc_buf);

	Assert(GinPageIsData(fc_page));

	if (GinPageIsLeaf(fc_page))
		return fc_dataBeginPlaceToPageLeaf(fc_btree, fc_buf, fc_stack, fc_insertdata,
										fc_ptp_workspace,
										fc_newlpage, fc_newrpage);
	else
		return fc_dataBeginPlaceToPageInternal(fc_btree, fc_buf, fc_stack,
											fc_insertdata, fc_updateblkno,
											fc_ptp_workspace,
											fc_newlpage, fc_newrpage);
}

/*
 * 在 beginPlaceToPage 决定可以容纳后执行数据插入。
 *
 * 这在一个临界区内被调用，XLOG 记录创建（如果需要）已经开始。目标缓冲区注册在槽 0 中。
 *
 * 调用内部或叶子页面的相关函数，因为它们的处理方式非常不同。
 */
static void fc_dataExecPlaceToPage(GinBtree fc_btree, Buffer fc_buf, GinBtreeStack *fc_stack,
					void *fc_insertdata, BlockNumber fc_updateblkno,
					void *fc_ptp_workspace)
{
	Page		fc_page = BufferGetPage(fc_buf);

	if (GinPageIsLeaf(fc_page))
		fc_dataExecPlaceToPageLeaf(fc_btree, fc_buf, fc_stack, fc_insertdata,
								fc_ptp_workspace);
	else
		fc_dataExecPlaceToPageInternal(fc_btree, fc_buf, fc_stack, fc_insertdata,
									fc_updateblkno, fc_ptp_workspace);
}

/*
 * 拆分内部页面并插入新数据。
 *
 * 将新临时页面返回到 *newlpage 和 *newrpage。
 * 原始缓冲区保持不变。
 */
static void fc_dataSplitPageInternal(GinBtree fc_btree, Buffer fc_origbuf,
					  GinBtreeStack *fc_stack,
					  void *fc_insertdata, BlockNumber fc_updateblkno,
					  Page *fc_newlpage, Page *fc_newrpage)
{
	Page		fc_oldpage = BufferGetPage(fc_origbuf);
	OffsetNumber fc_off = fc_stack->off;
	int			fc_nitems = GinPageGetOpaque(fc_oldpage)->maxoff;
	int			fc_nleftitems;
	int			fc_nrightitems;
	Size		fc_pageSize = PageGetPageSize(fc_oldpage);
	ItemPointerData fc_oldbound = *GinDataPageGetRightBound(fc_oldpage);
	ItemPointer fc_bound;
	Page		fc_lpage;
	Page		fc_rpage;
	OffsetNumber fc_separator;
	PostingItem fc_allitems[(BLCKSZ / sizeof(PostingItem)) + 1];

	fc_lpage = PageGetTempPage(fc_oldpage);
	fc_rpage = PageGetTempPage(fc_oldpage);
	GinInitPage(fc_lpage, GinPageGetOpaque(fc_oldpage)->flags, fc_pageSize);
	GinInitPage(fc_rpage, GinPageGetOpaque(fc_oldpage)->flags, fc_pageSize);

	/*
	 * 首先构建一个新的 PostingItems 列表，包括所有旧项和新项。
	 */
	memcpy(fc_allitems, GinDataPageGetPostingItem(fc_oldpage, FirstOffsetNumber),
		   (fc_off - 1) * sizeof(PostingItem));

	fc_allitems[fc_off - 1] = *((PostingItem *) fc_insertdata);
	memcpy(&fc_allitems[fc_off], GinDataPageGetPostingItem(fc_oldpage, fc_off),
		   (fc_nitems - (fc_off - 1)) * sizeof(PostingItem));
	fc_nitems++;

	/* 更新现有的下行链接以指向下一页 */
	PostingItemSetBlockNumber(&fc_allitems[fc_off], fc_updateblkno);

	/*
	 * 在创建新索引时，将尽可能多的元组放在左侧页面上，假设表从头到尾扫描。
	 * 这会将索引尽可能紧凑地打包。
	 */
	if (fc_btree->isBuild && GinPageRightMost(fc_oldpage))
		fc_separator = GinNonLeafDataPageGetFreeSpace(fc_rpage) / sizeof(PostingItem);
	else
		fc_separator = fc_nitems / 2;
	fc_nleftitems = fc_separator;
	fc_nrightitems = fc_nitems - fc_separator;

	memcpy(GinDataPageGetPostingItem(fc_lpage, FirstOffsetNumber),
		   fc_allitems,
		   fc_nleftitems * sizeof(PostingItem));
	GinPageGetOpaque(fc_lpage)->maxoff = fc_nleftitems;
	memcpy(GinDataPageGetPostingItem(fc_rpage, FirstOffsetNumber),
		   &fc_allitems[fc_separator],
		   fc_nrightitems * sizeof(PostingItem));
	GinPageGetOpaque(fc_rpage)->maxoff = fc_nrightitems;

	/*
	 * 还要为两个页面设置 pd_lower，像 GinDataPageAddPostingItem 所做的那样。
	 */
	GinDataPageSetDataSize(fc_lpage, fc_nleftitems * sizeof(PostingItem));
	GinDataPageSetDataSize(fc_rpage, fc_nrightitems * sizeof(PostingItem));

	/* 为左页面设置右边界 */
	fc_bound = GinDataPageGetRightBound(fc_lpage);
	*fc_bound = GinDataPageGetPostingItem(fc_lpage, fc_nleftitems)->key;

	/* 为右页面设置右边界 */
	*GinDataPageGetRightBound(fc_rpage) = fc_oldbound;

	/* 将临时页面返回给调用者 */
	*fc_newlpage = fc_lpage;
	*fc_newrpage = fc_rpage;
}

/*
 * 构造插入负载以插入给定缓冲区的下行链接。
 */
static void * fc_dataPrepareDownlink(GinBtree fc_btree, Buffer fc_lbuf)
{
	PostingItem *fc_pitem = palloc(sizeof(PostingItem));
	Page		fc_lpage = BufferGetPage(fc_lbuf);

	PostingItemSetBlockNumber(fc_pitem, BufferGetBlockNumber(fc_lbuf));
	fc_pitem->key = *GinDataPageGetRightBound(fc_lpage);

	return fc_pitem;
}

/*
 * 通过来自子节点的右边界值填充新根。
 * 也从 ginxlog 调用，不应使用 btree
 */
void ginDataFillRoot(GinBtree fc_btree, Page fc_root, BlockNumber fc_lblkno, Page fc_lpage, BlockNumber fc_rblkno, Page fc_rpage)
{
	PostingItem fc_li,
				fc_ri;

	fc_li.key = *GinDataPageGetRightBound(fc_lpage);
	PostingItemSetBlockNumber(&fc_li, fc_lblkno);
	GinDataPageAddPostingItem(fc_root, &fc_li, InvalidOffsetNumber);

	fc_ri.key = *GinDataPageGetRightBound(fc_rpage);
	PostingItemSetBlockNumber(&fc_ri, fc_rblkno);
	GinDataPageAddPostingItem(fc_root, &fc_ri, InvalidOffsetNumber);
}


/*** 处理已分解叶页的函数 ***/

/*
 * 将页面拆解为 disassembledLeaf 结构。
 */
static disassembledLeaf *
fc_disassembleLeaf(Page fc_page)
{
	disassembledLeaf *fc_leaf;
	GinPostingList *fc_seg;
	Pointer		fc_segbegin;
	Pointer		fc_segend;

	fc_leaf = palloc0(sizeof(disassembledLeaf));
	dlist_init(&fc_leaf->segments);

	if (GinPageIsCompressed(fc_page))
	{
		/*
		 * 为每个段创建一个 leafSegmentInfo 条目。
		 */
		fc_seg = GinDataLeafPageGetPostingList(fc_page);
		fc_segbegin = (Pointer) fc_seg;
		fc_segend = fc_segbegin + GinDataLeafPageGetPostingListSize(fc_page);
		while ((Pointer) fc_seg < fc_segend)
		{
			leafSegmentInfo *fc_seginfo = palloc(sizeof(leafSegmentInfo));

			fc_seginfo->action = GIN_SEGMENT_UNMODIFIED;
			fc_seginfo->seg = fc_seg;
			fc_seginfo->items = NULL;
			fc_seginfo->nitems = 0;
			dlist_push_tail(&fc_leaf->segments, &fc_seginfo->node);

			fc_seg = GinNextPostingListSegment(fc_seg);
		}
		fc_leaf->oldformat = false;
	}
	else
	{
		/*
		 * 预9.4格式未压缩页面由单个段表示，
		 * 其中包含一数组项。特殊情况是未压缩
		 * 页面不包含任何项目，表示为没有段。
		 */
		ItemPointer fc_uncompressed;
		int			fc_nuncompressed;
		leafSegmentInfo *fc_seginfo;

		fc_uncompressed = fc_dataLeafPageGetUncompressed(fc_page, &fc_nuncompressed);

		if (fc_nuncompressed > 0)
		{
			fc_seginfo = palloc(sizeof(leafSegmentInfo));

			fc_seginfo->action = GIN_SEGMENT_REPLACE;
			fc_seginfo->seg = NULL;
			fc_seginfo->items = palloc(fc_nuncompressed * sizeof(ItemPointerData));
			memcpy(fc_seginfo->items, fc_uncompressed, fc_nuncompressed * sizeof(ItemPointerData));
			fc_seginfo->nitems = fc_nuncompressed;

			dlist_push_tail(&fc_leaf->segments, &fc_seginfo->node);
		}

		fc_leaf->oldformat = true;
	}

	return fc_leaf;
}

/*
 * 将 newItems 分配给各个段。
 *
 * 任何获取新项目的段都会被解码，新项目将与旧项目合并。
 *
 * 如果添加了任何新项目，则返回 true。 false 意味着它们都是页面上现有项目的重复项。
 */
static bool fc_addItemsToLeaf(disassembledLeaf *fc_leaf, ItemPointer fc_newItems, int fc_nNewItems)
{
	dlist_iter	fc_iter;
	ItemPointer fc_nextnew = fc_newItems;
	int			fc_newleft = fc_nNewItems;
	bool		fc_modified = false;
	leafSegmentInfo *fc_newseg;

	/*
	 * 如果页面完全为空，则仅构造一个新段以容纳
	 * 所有新项目。
	 */
	if (dlist_is_empty(&fc_leaf->segments))
	{
		fc_newseg = palloc(sizeof(leafSegmentInfo));
		fc_newseg->seg = NULL;
		fc_newseg->items = fc_newItems;
		fc_newseg->nitems = fc_nNewItems;
		fc_newseg->action = GIN_SEGMENT_INSERT;
		dlist_push_tail(&fc_leaf->segments, &fc_newseg->node);
		return true;
	}

	dlist_foreach(fc_iter, &fc_leaf->segments)
	{
		leafSegmentInfo *fc_cur = (leafSegmentInfo *) dlist_container(leafSegmentInfo, node, fc_iter.cur);
		int			fc_nthis;
		ItemPointer fc_tmpitems;
		int			fc_ntmpitems;

		/*
		 * 多少新项目属于该段？
		 */
		if (!dlist_has_next(&fc_leaf->segments, fc_iter.cur))
			fc_nthis = fc_newleft;
		else
		{
			leafSegmentInfo *fc_next;
			ItemPointerData fc_next_first;

			fc_next = (leafSegmentInfo *) dlist_container(leafSegmentInfo, node,
													   dlist_next_node(&fc_leaf->segments, fc_iter.cur));
			if (fc_next->items)
				fc_next_first = fc_next->items[0];
			else
			{
				Assert(fc_next->seg != NULL);
				fc_next_first = fc_next->seg->first;
			}

			fc_nthis = 0;
			while (fc_nthis < fc_newleft && ginCompareItemPointers(&fc_nextnew[fc_nthis], &fc_next_first) < 0)
				fc_nthis++;
		}
		if (fc_nthis == 0)
			continue;

		/* 将新项目与现有项目合并。 */
		if (!fc_cur->items)
			fc_cur->items = ginPostingListDecode(fc_cur->seg, &fc_cur->nitems);

		/*
		 * 针对重要特殊情况的快速路径，即我们正在附加到
		 * 页面末尾： 不让页面上的最后一个段超过
		 * 目标，在发生之前创建一个新段。
		 */
		if (!dlist_has_next(&fc_leaf->segments, fc_iter.cur) &&
			ginCompareItemPointers(&fc_cur->items[fc_cur->nitems - 1], &fc_nextnew[0]) < 0 &&
			fc_cur->seg != NULL &&
			SizeOfGinPostingList(fc_cur->seg) >= GinPostingListSegmentTargetSize)
		{
			fc_newseg = palloc(sizeof(leafSegmentInfo));
			fc_newseg->seg = NULL;
			fc_newseg->items = fc_nextnew;
			fc_newseg->nitems = fc_nthis;
			fc_newseg->action = GIN_SEGMENT_INSERT;
			dlist_push_tail(&fc_leaf->segments, &fc_newseg->node);
			fc_modified = true;
			break;
		}

		fc_tmpitems = ginMergeItemPointers(fc_cur->items, fc_cur->nitems,
										fc_nextnew, fc_nthis,
										&fc_ntmpitems);
		if (fc_ntmpitems != fc_cur->nitems)
		{
			/*
			 * 如果没有重复项，跟踪添加的项目，以便我们
			 * 可以在稍后发出一个紧凑的 ADDITEMS WAL 记录。（似乎不值得重新检查哪些项目是重复的，
			 * 如果有的话）
			 */
			if (fc_ntmpitems == fc_nthis + fc_cur->nitems &&
				fc_cur->action == GIN_SEGMENT_UNMODIFIED)
			{
				fc_cur->action = GIN_SEGMENT_ADDITEMS;
				fc_cur->modifieditems = fc_nextnew;
				fc_cur->nmodifieditems = fc_nthis;
			}
			else
				fc_cur->action = GIN_SEGMENT_REPLACE;

			fc_cur->items = fc_tmpitems;
			fc_cur->nitems = fc_ntmpitems;
			fc_cur->seg = NULL;
			fc_modified = true;
		}

		fc_nextnew += fc_nthis;
		fc_newleft -= fc_nthis;
		if (fc_newleft == 0)
			break;
	}

	return fc_modified;
}

/*
 * 重新压缩所有已修改的段。
 *
 * 如果不是所有项目都适合两个页面（即在拆分后），我们将尽可能多地存储适合的项目，并将 *remaining 设置为第一个未适合的项目。
 * 如果所有项目都适合，则 *remaining 设置为无效。
 *
 * 如果页面必须拆分，则返回 true。
 */
static bool fc_leafRepackItems(disassembledLeaf *fc_leaf, ItemPointer fc_remaining)
{
	int			fc_pgused = 0;
	bool		fc_needsplit = false;
	dlist_iter	fc_iter;
	int			fc_segsize;
	leafSegmentInfo *fc_nextseg;
	int			fc_npacked;
	bool		fc_modified;
	dlist_node *fc_cur_node;
	dlist_node *fc_next_node;

	ItemPointerSetInvalid(fc_remaining);

	/*
	 * 不能在这里使用 dlist_foreach_modify，因为我们在迭代时插入相邻项目。
	 */
	for (fc_cur_node = dlist_head_node(&fc_leaf->segments);
		 fc_cur_node != NULL;
		 fc_cur_node = fc_next_node)
	{
		leafSegmentInfo *fc_seginfo = dlist_container(leafSegmentInfo, node,
												   fc_cur_node);

		if (dlist_has_next(&fc_leaf->segments, fc_cur_node))
			fc_next_node = dlist_next_node(&fc_leaf->segments, fc_cur_node);
		else
			fc_next_node = NULL;

		/* 如果必要，压缩发布列表 */
		if (fc_seginfo->action != GIN_SEGMENT_DELETE)
		{
			if (fc_seginfo->seg == NULL)
			{
				if (fc_seginfo->nitems > GinPostingListSegmentMaxSize)
					fc_npacked = 0;	/* 没有机会适合。 */
				else
				{
					fc_seginfo->seg = ginCompressPostingList(fc_seginfo->items,
														  fc_seginfo->nitems,
														  GinPostingListSegmentMaxSize,
														  &fc_npacked);
				}
				if (fc_npacked != fc_seginfo->nitems)
				{
					/*
					 * 太大了。再次压缩到目标大小，并
					 * 创建一个新段以表示剩余项目。
					 * 新段在该段之后插入，因此将在
					 * 本循环的下一次迭代中处理。
					 */
					if (fc_seginfo->seg)
						pfree(fc_seginfo->seg);
					fc_seginfo->seg = ginCompressPostingList(fc_seginfo->items,
														  fc_seginfo->nitems,
														  GinPostingListSegmentTargetSize,
														  &fc_npacked);
					if (fc_seginfo->action != GIN_SEGMENT_INSERT)
						fc_seginfo->action = GIN_SEGMENT_REPLACE;

					fc_nextseg = palloc(sizeof(leafSegmentInfo));
					fc_nextseg->action = GIN_SEGMENT_INSERT;
					fc_nextseg->seg = NULL;
					fc_nextseg->items = &fc_seginfo->items[fc_npacked];
					fc_nextseg->nitems = fc_seginfo->nitems - fc_npacked;
					fc_next_node = &fc_nextseg->node;
					dlist_insert_after(fc_cur_node, fc_next_node);
				}
			}

			/*
			 * 如果段非常小，则将其与下一个段合并。
			 */
			if (SizeOfGinPostingList(fc_seginfo->seg) < GinPostingListSegmentMinSize && fc_next_node)
			{
				int			fc_nmerged;

				fc_nextseg = dlist_container(leafSegmentInfo, node, fc_next_node);

				if (fc_seginfo->items == NULL)
					fc_seginfo->items = ginPostingListDecode(fc_seginfo->seg,
														  &fc_seginfo->nitems);
				if (fc_nextseg->items == NULL)
					fc_nextseg->items = ginPostingListDecode(fc_nextseg->seg,
														  &fc_nextseg->nitems);
				fc_nextseg->items =
					ginMergeItemPointers(fc_seginfo->items, fc_seginfo->nitems,
										 fc_nextseg->items, fc_nextseg->nitems,
										 &fc_nmerged);
				Assert(fc_nmerged == fc_seginfo->nitems + fc_nextseg->nitems);
				fc_nextseg->nitems = fc_nmerged;
				fc_nextseg->seg = NULL;

				fc_nextseg->action = GIN_SEGMENT_REPLACE;
				fc_nextseg->modifieditems = NULL;
				fc_nextseg->nmodifieditems = 0;

				if (fc_seginfo->action == GIN_SEGMENT_INSERT)
				{
					dlist_delete(fc_cur_node);
					continue;
				}
				else
				{
					fc_seginfo->action = GIN_SEGMENT_DELETE;
					fc_seginfo->seg = NULL;
				}
			}

			fc_seginfo->items = NULL;
			fc_seginfo->nitems = 0;
		}

		if (fc_seginfo->action == GIN_SEGMENT_DELETE)
			continue;

		/*
		 * 好的，我们现在已经有了这个段的压缩版本，准备
		 * 复制到页面。我们是否超出了适合一个页面的大小？
		 */
		fc_segsize = SizeOfGinPostingList(fc_seginfo->seg);
		if (fc_pgused + fc_segsize > GinDataPageMaxDataSize)
		{
			if (!fc_needsplit)
			{
				/* 切换到右页面 */
				Assert(fc_pgused > 0);
				fc_leaf->lastleft = dlist_prev_node(&fc_leaf->segments, fc_cur_node);
				fc_needsplit = true;
				fc_leaf->lsize = fc_pgused;
				fc_pgused = 0;
			}
			else
			{
				/*
				 * 填充了两个页面。我们构造的最后一个段未能
				 * 适应。
				 */
				*fc_remaining = fc_seginfo->seg->first;

				/*
				 * 从列表中移除所有不符合的段。
				 */
				while (dlist_has_next(&fc_leaf->segments, fc_cur_node))
					dlist_delete(dlist_next_node(&fc_leaf->segments, fc_cur_node));
				dlist_delete(fc_cur_node);
				break;
			}
		}

		fc_pgused += fc_segsize;
	}

	if (!fc_needsplit)
	{
		fc_leaf->lsize = fc_pgused;
		fc_leaf->rsize = 0;
	}
	else
		fc_leaf->rsize = fc_pgused;

	Assert(fc_leaf->lsize <= GinDataPageMaxDataSize);
	Assert(fc_leaf->rsize <= GinDataPageMaxDataSize);

	/*
	 * 对第一个被修改的段之后的每个段进行 palloc 的副本，
	 * 因为在我们开始将项目复制到原始页面时，可能会覆盖现有段。
	 */
	fc_modified = false;
	dlist_foreach(fc_iter, &fc_leaf->segments)
	{
		leafSegmentInfo *fc_seginfo = dlist_container(leafSegmentInfo, node,
												   fc_iter.cur);

		if (!fc_modified && fc_seginfo->action != GIN_SEGMENT_UNMODIFIED)
		{
			fc_modified = true;
		}
		else if (fc_modified && fc_seginfo->action == GIN_SEGMENT_UNMODIFIED)
		{
			GinPostingList *fc_tmp;

			fc_segsize = SizeOfGinPostingList(fc_seginfo->seg);
			fc_tmp = palloc(fc_segsize);
			memcpy(fc_tmp, fc_seginfo->seg, fc_segsize);
			fc_seginfo->seg = fc_tmp;
		}
	}

	return fc_needsplit;
}


/*** 导出到 GIN 代码其余部分的函数 ***/

/*
 * 创建一个新的包含给定 TID 的发布树。返回新发布树根的页面
 * 编号。
 *
 * items[] 必须按排序顺序排列且不重复。
 */
BlockNumber createPostingTree(Relation fc_index, ItemPointerData *fc_items, uint32 fc_nitems,
				  GinStatsData *fc_buildStats, Buffer fc_entrybuffer)
{
	BlockNumber fc_blkno;
	Buffer		fc_buffer;
	Page		fc_tmppage;
	Page		fc_page;
	Pointer		fc_ptr;
	int			fc_nrootitems;
	int			fc_rootsize;
	bool		fc_is_build = (fc_buildStats != NULL);

	/* 首先在内存中构建新的根页面。 */
	fc_tmppage = (Page) palloc(BLCKSZ);
	GinInitPage(fc_tmppage, GIN_DATA | GIN_LEAF | GIN_COMPRESSED, BLCKSZ);
	GinPageGetOpaque(fc_tmppage)->rightlink = InvalidBlockNumber;

	/*
	 * 尽可能多地将项目写入根页面。以每个最大
	 * GinPostingListSegmentMaxSize 字节的段。
	 */
	fc_nrootitems = 0;
	fc_rootsize = 0;
	fc_ptr = (Pointer) GinDataLeafPageGetPostingList(fc_tmppage);
	while (fc_nrootitems < fc_nitems)
	{
		GinPostingList *fc_segment;
		int			fc_npacked;
		int			fc_segsize;

		fc_segment = ginCompressPostingList(&fc_items[fc_nrootitems],
										 fc_nitems - fc_nrootitems,
										 GinPostingListSegmentMaxSize,
										 &fc_npacked);
		fc_segsize = SizeOfGinPostingList(fc_segment);
		if (fc_rootsize + fc_segsize > GinDataPageMaxDataSize)
			break;

		memcpy(fc_ptr, fc_segment, fc_segsize);
		fc_ptr += fc_segsize;
		fc_rootsize += fc_segsize;
		fc_nrootitems += fc_npacked;
		pfree(fc_segment);
	}
	GinDataPageSetDataSize(fc_tmppage, fc_rootsize);

	/*
	 * 一切就绪。获取一个新的物理页面，并将内存页面复制到其中。
	 */
	fc_buffer = GinNewBuffer(fc_index);
	fc_page = BufferGetPage(fc_buffer);
	fc_blkno = BufferGetBlockNumber(fc_buffer);

	/*
	 * 将条目树叶（包含发布
	 * 列表）的任何谓词锁复制到发布树。
	 */
	PredicateLockPageSplit(fc_index, BufferGetBlockNumber(fc_entrybuffer), fc_blkno);

	START_CRIT_SECTION();

	PageRestoreTempPage(fc_tmppage, fc_page);
	MarkBufferDirty(fc_buffer);

	if (RelationNeedsWAL(fc_index) && !fc_is_build)
	{
		XLogRecPtr	fc_recptr;
		ginxlogCreatePostingTree fc_data;

		fc_data.size = fc_rootsize;

		XLogBeginInsert();
		XLogRegisterData((char *) &fc_data, sizeof(ginxlogCreatePostingTree));

		XLogRegisterData((char *) GinDataLeafPageGetPostingList(fc_page),
						 fc_rootsize);
		XLogRegisterBuffer(0, fc_buffer, REGBUF_WILL_INIT);

		fc_recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_CREATE_PTREE);
		PageSetLSN(fc_page, fc_recptr);
	}

	UnlockReleaseBuffer(fc_buffer);

	END_CRIT_SECTION();

	/* 在构建索引期间，计算新添加的数据页面 */
	if (fc_buildStats)
		fc_buildStats->nDataPages++;

	elog(DEBUG2, "created GIN posting tree with %d items", fc_nrootitems);

	/*
	 * 将任何剩余的 TID 添加到新创建的发布树中。
	 */
	if (fc_nitems > fc_nrootitems)
	{
		ginInsertItemPointers(fc_index, fc_blkno,
							  fc_items + fc_nrootitems,
							  fc_nitems - fc_nrootitems,
							  fc_buildStats);
	}

	return fc_blkno;
}

static void fc_ginPrepareDataScan(GinBtree fc_btree, Relation fc_index, BlockNumber fc_rootBlkno)
{
	memset(fc_btree, 0, sizeof(GinBtreeData));

	fc_btree->index = fc_index;
	fc_btree->rootBlkno = fc_rootBlkno;

	fc_btree->findChildPage = fc_dataLocateItem;
	fc_btree->getLeftMostChild = fc_dataGetLeftMostPage;
	fc_btree->isMoveRight = fc_dataIsMoveRight;
	fc_btree->findItem = NULL;
	fc_btree->findChildPtr = fc_dataFindChildPtr;
	fc_btree->beginPlaceToPage = fc_dataBeginPlaceToPage;
	fc_btree->execPlaceToPage = fc_dataExecPlaceToPage;
	fc_btree->fillRoot = ginDataFillRoot;
	fc_btree->prepareDownlink = fc_dataPrepareDownlink;

	fc_btree->isData = true;
	fc_btree->fullScan = false;
	fc_btree->isBuild = false;
}

/*
 * 插入项目指针数组，可能会执行多个树扫描（非常罕见）
 */
void ginInsertItemPointers(Relation fc_index, BlockNumber fc_rootBlkno,
					  ItemPointerData *fc_items, uint32 fc_nitem,
					  GinStatsData *fc_buildStats)
{
	GinBtreeData fc_btree;
	GinBtreeDataLeafInsertData fc_insertdata;
	GinBtreeStack *fc_stack;

	fc_ginPrepareDataScan(&fc_btree, fc_index, fc_rootBlkno);
	fc_btree.isBuild = (fc_buildStats != NULL);
	fc_insertdata.items = fc_items;
	fc_insertdata.nitem = fc_nitem;
	fc_insertdata.curitem = 0;

	while (fc_insertdata.curitem < fc_insertdata.nitem)
	{
		/* 搜索第一个项目应该放入的叶页面 */
		fc_btree.itemptr = fc_insertdata.items[fc_insertdata.curitem];
		fc_stack = ginFindLeafPage(&fc_btree, false, true, NULL);

		ginInsertValue(&fc_btree, fc_stack, &fc_insertdata, fc_buildStats);
	}
}

/*
 * 在发布树上开始新的扫描。
 */
GinBtreeStack *
ginScanBeginPostingTree(GinBtree fc_btree, Relation fc_index, BlockNumber fc_rootBlkno,
						Snapshot fc_snapshot)
{
	GinBtreeStack *fc_stack;

	fc_ginPrepareDataScan(fc_btree, fc_index, fc_rootBlkno);

	fc_btree->fullScan = true;

	fc_stack = ginFindLeafPage(fc_btree, true, false, fc_snapshot);

	return fc_stack;
}
